<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="utf-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no" />

    <title></title>
    <link rel="stylesheet" href="dist/reveal.css" />
    <link rel="stylesheet" href="dist/theme/black.css" id="theme" />
    <link rel="stylesheet" href="plugin/highlight/zenburn.css" />
	<link rel="stylesheet" href="css/layout.css" />
	<link rel="stylesheet" href="plugin/customcontrols/style.css">



    <script defer src="dist/fontawesome/all.min.js"></script>

	<script type="text/javascript">
		var forgetPop = true;
		function onPopState(event) {
			if(forgetPop){
				forgetPop = false;
			} else {
				parent.postMessage(event.target.location.href, "app://obsidian.md");
			}
        }
		window.onpopstate = onPopState;
		window.onmessage = event => {
			if(event.data == "reload"){
				window.document.location.reload();
			}
			forgetPop = true;
		}

		function fitElements(){
			const itemsToFit = document.getElementsByClassName('fitText');
			for (const item in itemsToFit) {
				if (Object.hasOwnProperty.call(itemsToFit, item)) {
					var element = itemsToFit[item];
					fitElement(element,1, 1000);
					element.classList.remove('fitText');
				}
			}
		}

		function fitElement(element, start, end){

			let size = (end + start) / 2;
			element.style.fontSize = `${size}px`;

			if(Math.abs(start - end) < 1){
				while(element.scrollHeight > element.offsetHeight){
					size--;
					element.style.fontSize = `${size}px`;
				}
				return;
			}

			if(element.scrollHeight > element.offsetHeight){
				fitElement(element, start, size);
			} else {
				fitElement(element, size, end);
			}		
		}


		document.onreadystatechange = () => {
			fitElements();
			if (document.readyState === 'complete') {
				if (window.location.href.indexOf("?export") != -1){
					parent.postMessage(event.target.location.href, "app://obsidian.md");
				}
				if (window.location.href.indexOf("print-pdf") != -1){
					let stateCheck = setInterval(() => {
						clearInterval(stateCheck);
						window.print();
					}, 250);
				}
			}
	};


        </script>
  </head>
  <body>
    <div class="reveal">
      <div class="slides"><section  data-markdown><script type="text/template"><!-- .slide: class="has-dark-background drop" data-background-color="rgb(54,69,89)" -->
<div class="" style="position: absolute; left: 0px; top: 0px; height: 1200px; width: 1920px; min-height: 1200px; display: flex; flex-direction: column; align-items: center; justify-content: center" absolute="true">

# K 近邻算法


<div class="" style="opacity: 0.5; position: absolute; left: 10%; top: 92%; height: 8%; width: 80%; display: flex; flex-direction: column; align-items: center; justify-content: center" >

 授课教师：朱秋扬
 @ 安徽科技学院 信息与网络工程学院
</div>
</div></script></section><section  data-markdown><script type="text/template"><!-- .slide: class="has-dark-background drop" data-background-color="#364559" -->
<div class="" style="position: absolute; left: 0px; top: 0px; height: 1200px; width: 1920px; min-height: 1200px; display: flex; flex-direction: column; align-items: center; justify-content: center" absolute="true">

## 回顾: 机器学习


<img src="ml_image/ml-silu.png" alt="" style="object-fit: scale-down">
</div></script></section><section  data-markdown><script type="text/template"><!-- .slide: class="has-dark-background drop" data-background-color="#364559" -->
<div class="" style="position: absolute; left: 0px; top: 0px; height: 1200px; width: 1920px; min-height: 1200px; display: flex; flex-direction: column; align-items: center; justify-content: center" absolute="true">

<img src="ml_image/Pasted image 20230419095814.png" alt="" style="object-fit: scale-down">
</div></script></section><section  data-markdown><script type="text/template"><!-- .slide: class="has-dark-background drop" data-background-color="#364559" -->
<div class="" style="position: absolute; left: 0px; top: 0px; height: 1200px; width: 1920px; min-height: 1200px; display: flex; flex-direction: column; align-items: center; justify-content: center" absolute="true">

## 什么是 KNN 算法?


-   最简单的分类算法
 
-   对一组观测数据进行**度量**，每一条数据包含 **M**个特征，例如 `$x_1$`，`$x_2$`，`$x_3$`，... , `$x_m$`

- 它实现将距离近的样本点划为同一类别，KNN 中的K指的是近邻个数，也就是最近的K个点，根据它距离最近的K个点是什么类别来判断属于哪个类别。

- 基于实例的学习（Instance-Based Learning）
- 懒惰学习（Lazy Learning）
</div></script></section><section  data-markdown><script type="text/template"><!-- .slide: class="has-dark-background drop" data-background-color="#364559" -->
<div class="" style="position: absolute; left: 0px; top: 0px; height: 1200px; width: 1920px; min-height: 1200px; display: flex; flex-direction: column; align-items: center; justify-content: center" absolute="true">

<div class="" style="position: absolute; left: 0%; top: 0%; height: 10%; width: 100%; display: flex; flex-direction: column; align-items: center; justify-content: center" >

## KNN 算法的动态演示
</div>

<div class="has-dark-background" style="background-color: #204056; position: absolute; left: 0%; top: 15%; height: 70%; width: 70%; display: flex; flex-direction: column; align-items: center; justify-content: center" >


<img src="https://www.gairuo.com/file/pic/2021/01/nearest_neighbor.gif" alt="image|1500" style="width: 1500px; object-fit: fill">

</div>

<div class="" style="position: absolute; left: 70%; top: 15%; height: 70%; width: 30%; display: flex; flex-direction: column; align-items: center; justify-content: center" >

## 1. K = 1
<!-- .element: style="color: aqua" -->
## 2. K = 2
<!-- .element: style="color: aqua" -->
## 3. K = 3
<!-- .element: style="color: aqua" -->
## 4. K = 4
<!-- .element: style="color: gray" -->
## 5. K = 5
<!-- .element: style="color: red" -->
</div>

<div class="fadeIn" style="font-size: 2rem; position: absolute; left: 0%; top: 80%; height: 20%; width: 100%; display: flex; flex-direction: column; align-items: center; justify-content: center" >

当 K 取值不同的时候，判别的结果是不同的。所以该算法中 K 值如何选择将非常重要，因为它会影响到我们最终的结果。
</div>
</div></script></section><section  data-markdown><script type="text/template"><!-- .slide: class="has-dark-background drop" data-background-color="#364559" -->
<div class="" style="position: absolute; left: 0px; top: 0px; height: 1200px; width: 1920px; min-height: 1200px; display: flex; flex-direction: column; align-items: center; justify-content: center" absolute="true">

<div class="" style="padding: 0 30px; box-sizing: border-box; position: absolute; left: 5%; top: 25%; height: 40%; width: 32%; display: flex; flex-direction: column; align-items: flex-start; justify-content: space-evenly" align="left">


# 思想原理
#### 「人以群分，物以类聚」<br>「近朱者赤，近墨者黑」
</div>

<img src="https://www.gairuo.com/file/pic/2021/01/knn-metrics.png" alt="KNN 最近邻算法" style="position: absolute; left: 40%; top: 18%; height: 62%; width: 45%; display: flex; flex-direction: column; align-items: center; justify-content: center; object-fit: fill">


其中的 K 就是 K 个最近的邻居的意思。KNN 的原理就是当预测一个待分类的值 x 的时候，通过计算找出离它距离最近的 K 个样本，然后由这个 K 个样本投票决定 x 归为哪一类。我们也可以看到实现这个算法的两个核心问题是计算距离和选取 K 的取值。 <!-- .element: style="font-size: 24px; background-color: #EEB73F; padding: 50px; box-sizing: border-box; position: absolute; left: 65%; top: 65%; height: 27%; width: 32%; display: flex; flex-direction: column; align-items: center; justify-content: space-evenly" class="has-light-background" align="justify" -->
</div></script></section><section  data-markdown><script type="text/template"><!-- .slide: class="has-light-background drop" data-background-color="white" -->
<div class="" style="position: absolute; left: 0px; top: 0px; height: 1200px; width: 1920px; min-height: 1200px; display: flex; flex-direction: column; align-items: center; justify-content: center" absolute="true">

<img src="https://picsum.photos/id/885/800/1220" alt="" style="max-height: 100%; max-width: 100%; position: absolute; left: 10%; top: 10%; height: 80%; width: 40%; display: flex; flex-direction: column; align-items: center; justify-content: center; object-fit: fill">


<div class="has-light-background" style="background-color: white; padding: 26px; box-sizing: border-box; opacity: 0.5; position: absolute; left: 18%; top: 40%; height: 40%; width: 27%; display: flex; flex-direction: column; align-items: center; justify-content: center" >
</div>

<div class="" style="padding: 26px; box-sizing: border-box; position: absolute; left: 18%; top: 40%; height: 40%; width: 27%; display: flex; flex-direction: column; align-items: center; justify-content: center" >


## 距离计算

KNN 算法中用样本之间的距离来衡量样本之间的相似度。
<!-- .element: style="font-size: 28px; display: flex; flex-direction: column; align-items: center; justify-content: space-evenly" align="justify" -->
</div>


<div class="has-light-background" style="background-color: #EEB73F; padding: 100px 100px; box-sizing: border-box; position: absolute; left: 50%; top: 0%; height: 100%; width: 50%; display: flex; flex-direction: column; align-items: center; justify-content: space-evenly" align="justify">


#### 常用的距离有：

-  欧氏距离（Euclidean Distance)
-  曼哈顿距离（Manhattan Distance)
-  明氏距离（Minkowski Distance)
-  切比雪夫距离（Chebyshev Distance)
-  马氏距离
-  汉明距离
-  夹角余弦
-  杰卡德相似系数

#### 

其中**欧式距离**最为常用

n 个 p 维样本`$ x_i $`其欧式距离公式如下：

`$d(x_i,x_j)=\sqrt{\sum_{k=1}^p(x_{ik}%20-%20x_{jk})^2})$`

</div>
</div></script></section><section  data-markdown><script type="text/template"><!-- .slide: class="has-dark-background drop" data-background-color="#364559" -->
<div class="" style="position: absolute; left: 0px; top: 0px; height: 1200px; width: 1920px; min-height: 1200px; display: flex; flex-direction: column; align-items: center; justify-content: center" absolute="true">

## 常用距离（图示）

<img src="ml_image/distances.webp" alt="" style="width: 800px; height: 800px; object-fit: fill">
</div></script></section><section  data-markdown><script type="text/template"><!-- .slide: class="drop" -->
<div class="" style="position: absolute; left: 0px; top: 0px; height: 1200px; width: 1920px; min-height: 1200px; display: flex; flex-direction: column; align-items: center; justify-content: center" absolute="true">

<div class="has-dark-background" style="background-color: #204056; position: absolute; left: 0%; top: 0%; height: 100%; width: 30%; display: flex; flex-direction: column; align-items: center; justify-content: center" >

## K近邻算法步骤
</div>

<div class="" style="position: absolute; left: 30%; top: 0%; height: 100%; width: 70%; display: flex; flex-direction: column; align-items: center; justify-content: center" >

1. 计算已知类别数据集中的点与当前点之间的距离；
2. 按照距离递增次序排序；
3. 选取与当前点距离最小的k个点；
4. 确定前k个点所在类别的出现频率；
5. 返回前k个点出现频率最高的类别作为当前点的预测类别。
</div>
</div></script></section><section  data-markdown><script type="text/template"><!-- .slide: class="drop" -->
<div class="" style="position: absolute; left: 0px; top: 0px; height: 1200px; width: 1920px; min-height: 1200px; display: flex; flex-direction: column; align-items: center; justify-content: center" absolute="true">

## 代码实现

> 以手写数字识别系统为例

<img src="ml_image/Pasted image 20230419120240.png" alt="" style="object-fit: scale-down">
</div></script></section><section  data-markdown><script type="text/template"><!-- .slide: class="drop" -->
<div class="" style="position: absolute; left: 0px; top: 0px; height: 1200px; width: 1920px; min-height: 1200px; display: flex; flex-direction: column; align-items: center; justify-content: center" absolute="true">

## 代码实现

```py
# Hamming Distance
def hamm(str1, str2):
    return sum([ a!=b for (a, b) in zip(str1, str2)])
```

```py
def knn(inX, df, k):
	# 1. 计算输入与所有样本的距离
    dist = df.iloc[:,0].apply(
        lambda img: sum([ a!=b for (a, b) in zip(inX, img)])
    )
    dist_l = pd.DataFrame({
        "dist": dist,
        "label": df.iloc[:, -1]
    })
    # 2. 把距离升序排序，提取前 k 项
    dist_k = dist_l.sort_values(by="dist").iloc[:k]
    # 3. 获得频率最高的标签
    pred = (dist_k.value_counts("label")).index[0]
    return pred
```

```py
digitsTest(train, test, 3)
> 0.9894291754756871
```
在此例子中，在 K 值 为 3 的情况下，手写数字识别的准确率为 **98.9%**
</div></script></section><section  data-markdown><script type="text/template"><!-- .slide: class="drop" -->
<div class="" style="position: absolute; left: 0px; top: 0px; height: 1200px; width: 1920px; min-height: 1200px; display: flex; flex-direction: column; align-items: center; justify-content: center" absolute="true">

## 算法优点
<!-- .element: style="position: absolute; left: 60%; top: 3%; height: 35%; width: 30%; display: flex; flex-direction: column; align-items: flex-start; justify-content: space-evenly" align="left" -->

<div class="" style="font-size: 38px; position: absolute; left: 12%; top: 12%; height: 35%; width: 45%; display: flex; flex-direction: column; align-items: center; justify-content: center" >

-   **简单**，易于理解，易于实现，无需估计参数
-   对数据没有假设，**准确度高**，对异常点不敏感
</div>

#### 算法缺点<!-- .element: style="position: absolute; left: 11%; top: 55%; height: 5%; width: 15%; display: flex; flex-direction: column; align-items: flex-start; justify-content: space-evenly" align="left" -->

<div class="" style="font-size: 24px; position: absolute; left: 11%; top: 58%; height: 30%; width: 30%; display: flex; flex-direction: column; align-items: center; justify-content: space-evenly" align="justify">

-   **计算量太大**，尤其是特征数非常多的时候。每一个待分类文本都要计算它到全体已知样本的距离，才能得到它的第K个最近邻点。
-   样本不平衡的时候，**对稀有类别的预测准确率低**。当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。
</div>

<img src="ml_image/Pasted image 20230419112945.png" alt="" style="position: absolute; left: 47%; top: 40%; height: 45%; width: 30%; display: flex; flex-direction: column; align-items: center; justify-content: center; object-fit: fill">
</div></script></section><section  data-markdown><script type="text/template"><!-- .slide: class="drop" -->
<div class="" style="position: absolute; left: 0px; top: 0px; height: 1200px; width: 1920px; min-height: 1200px; display: flex; flex-direction: column; align-items: center; justify-content: center" absolute="true">

### KNN  算法启示
<!-- .element: style="color: #EEB73F" -->

### 1. 物以类聚 
>学习优秀的特征
### 2. 知己知彼
>取长补短
### 3. 善于总结
> 透过现象看本质，提炼规律
### 4. 灵活运用
> 举一反三，而非生搬硬套

<img src="ml_image/Pasted image 20230419132008.png" alt="" style="width: 1350px; height: 150px; object-fit: fill">
</div></script></section><section  data-markdown><script type="text/template"><!-- .slide: class="drop" -->
<div class="" style="position: absolute; left: 0px; top: 0px; height: 1200px; width: 1920px; min-height: 1200px; display: flex; flex-direction: column; align-items: center; justify-content: center" absolute="true">

# 感谢
</div></script></section></div>
    </div>

    <script src="dist/reveal.js"></script>

    <script src="plugin/markdown/markdown.js"></script>
    <script src="plugin/highlight/highlight.js"></script>
    <script src="plugin/zoom/zoom.js"></script>
    <script src="plugin/notes/notes.js"></script>
    <script src="plugin/math/math.js"></script>
	<script src="plugin/mermaid/mermaid.js"></script>
	<script src="plugin/chart/chart.min.js"></script>
	<script src="plugin/chart/plugin.js"></script>
	<script src="plugin/customcontrols/plugin.js"></script>

    <script>
      function extend() {
        var target = {};
        for (var i = 0; i < arguments.length; i++) {
          var source = arguments[i];
          for (var key in source) {
            if (source.hasOwnProperty(key)) {
              target[key] = source[key];
            }
          }
        }
        return target;
      }

	  function isLight(color) {
		let hex = color.replace('#', '');

		// convert #fff => #ffffff
		if(hex.length == 3){
			hex = `${hex[0]}${hex[0]}${hex[1]}${hex[1]}${hex[2]}${hex[2]}`;
		}

		const c_r = parseInt(hex.substr(0, 2), 16);
		const c_g = parseInt(hex.substr(2, 2), 16);
		const c_b = parseInt(hex.substr(4, 2), 16);
		const brightness = ((c_r * 299) + (c_g * 587) + (c_b * 114)) / 1000;
		return brightness > 155;
	}

	var bgColor = getComputedStyle(document.documentElement).getPropertyValue('--r-background-color').trim();
	var isLight = isLight(bgColor);

	if(isLight){
		document.body.classList.add('has-light-background');
	} else {
		document.body.classList.add('has-dark-background');
	}

      // default options to init reveal.js
      var defaultOptions = {
        controls: true,
        progress: true,
        history: true,
        center: true,
        transition: 'default', // none/fade/slide/convex/concave/zoom
        plugins: [
          RevealMarkdown,
          RevealHighlight,
          RevealZoom,
          RevealNotes,
          RevealMath.MathJax3,
		  RevealMermaid,
		  RevealChart,
		  RevealCustomControls,
        ],


    	allottedTime: 120 * 1000,

		mathjax3: {
			mathjax: 'plugin/math/mathjax/tex-mml-chtml.js',
		},
		markdown: {
		  gfm: true,
		  mangle: true,
		  pedantic: false,
		  smartLists: false,
		  smartypants: false,
		},

		mermaid: {
			theme: isLight ? 'default' : 'dark',
		},

		customcontrols: {
			controls: [
			]
		},
      };

      // options from URL query string
      var queryOptions = Reveal().getQueryHash() || {};

      var options = extend(defaultOptions, {"width":1920,"height":1200,"margin":0,"controls":true,"progress":true,"slideNumber":false,"transition":"slide","transitionSpeed":"default"}, queryOptions);
    </script>

    <script>
      Reveal.initialize(options);
    </script>
  </body>

  <!-- created with Advanced Slides -->
</html>
